#!/usr/bin/python3.5

# -*- coding: utf-8 -*-

class Solution:
    def fourSum(self, nums, target):
        n = len(nums)
        if n<4:
            return []
        nums.sort()
        res=[]
        i = 0
        while i< n-3:
            # while nums[i]==nums[i+1]:
            #     i+=1
            j = i+1
            while j< n-2:

                 k = j+1
                 m = n-1

                 while k<m:
                     sum_4 = nums[i]+nums[j]+nums[k]+nums[m]
                     if sum_4 == target:
                         res.append([nums[i],nums[j],nums[k],nums[m]])
                         k += 1
                         while k<m and nums[k] == nums[k - 1]:
                             k += 1
                     elif sum_4<target:
                         k+=1
                         while k<m and nums[k]==nums[k-1]:
                             k+=1

                     else:
                         m -= 1
                         while m>k and nums[m] == nums[m + 1]:
                             m-= 1
                 j += 1
                 while j< n-2 and nums[j] == nums[j - 1]:
                     j += 1

            i+=1
            while i<n-3 and nums[i] == nums[i - 1]:
                i+=1
        return res





if __name__=='__main__':
    # arr=[int(x) for x in input().strip().split(' ')]
    arr=[2,2,2,2,2]
    target = 8
    solution=Solution()
    a = solution.fourSum(arr,target)
    print(a)

